package com.ljy.my_study.leetcode.括号生成;

import java.util.ArrayList;
import java.util.List;

/** 
* @author James
* @date 2018年9月17日 
*/
public class KuohaoUtils {
	public static boolean isValid(String str) {
		if(str==null) {
			return false;
		}
		if(str!=null&&str.isEmpty()) {
			return true;
		}
		char[] cArr=str.toCharArray();
		if(cArr.length%2!=0) {
			return false;
		}
		List<Integer> smallLeftIndexList=new ArrayList<>();
		List<Integer> middleLeftIndexList=new ArrayList<>();
		List<Integer> bigLeftIndexList=new ArrayList<>();
		for(int i=0;i<cArr.length;i++) {
			switch(cArr[i]) {
			case '(':smallLeftIndexList.add(i);continue;
			case '[':middleLeftIndexList.add(i);continue;
			case '{':bigLeftIndexList.add(i);continue;
			}
			int max=getLastLeftIndex(smallLeftIndexList,middleLeftIndexList,bigLeftIndexList);
			if(cArr[i]==')') {
				if(!checkList(smallLeftIndexList,cArr[max],cArr[i])) {
					return false;
				}
			}else if(cArr[i]==']') {
				if(!checkList(middleLeftIndexList,cArr[max],cArr[i])) {
					return false;
				}
			}else if(cArr[i]=='}') {
				if(!checkList(bigLeftIndexList,cArr[max],cArr[i])) {
					return false;
				}
			}
		}
		if(smallLeftIndexList.isEmpty()&&middleLeftIndexList.isEmpty()&&bigLeftIndexList.isEmpty()) {
			return true;
		}
		return false;
	}
	
	private static int getLastLeftIndex(List<Integer> l1,List<Integer> l2,List<Integer> l3) {
		int i1,i2,i3=0;
		 if(l1.isEmpty()) {
			 i1=0;
		 }else {
			 i1=l1.get(l1.size()-1);
		 }
		 if(l2.isEmpty()) {
			 i2=0;
		 }else {
			 i2=l2.get(l2.size()-1);
		 }
		 if(l3.isEmpty()) {
			 i3=0;
		 }else {
			 i3=l3.get(l3.size()-1);
		 }
		 int max=0;
		 if(i1>i2) {
			 max=i1;
		 }else {
			 max=i2;
		 }
		 if(max<i3) {
			 max=i3;
		 }
		 return max;
	}
	
	
	private static boolean checkList(List<Integer> list,char left,char right) {
		if(list.isEmpty()) {
			return false;
		}
		if(!((left=='('&&right==')')
				||(left=='['&&right==']')
				||(left=='{'&&right=='}'))) {
			return false;
		}
		
		list.remove(list.size()-1);
		return true;
	}
}
